CoinCombinations.java

packagesection12_Backtracking;

publicclassCoinCombinations {

staticintcount = 0;

publicstaticvoidmain(String[] args) {

int[] denominations = { 2, 3, 5, 6 };
intamount = 10;
Stringans = "";
intcurrentSum = 0;
intlastCoinIdx = 0;
coinCombinations(denominations, amount, ans, currentSum, lastCoinIdx);
 }

staticvoidcoinCombinations(int[] coins, intamount, Stringans, intcurrentSum, intlastCoinIdx) {

if (currentSum == amount) {
count++;
System.out.println(count + ". " + ans);
return;
 }

if (currentSum > amount) {
return;
 }

for (intcurrentCoin = lastCoinIdx; currentCoin < coins.length; currentCoin++) {

coinCombinations(coins, amount, ans + coins[currentCoin], currentSum + coins[currentCoin], currentCoin);
 }

 }

}

/*output 
1. 22222
2. 2233
3. 226
4. 235
5. 55
 */